class Solution {
private:
    string num1[9] = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    string num2[10] = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string num3[8] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    void ans_append(string val, string& ans) {
        if (ans.size() == 0) {
            ans += val;
        } else {
            ans += " " + val;
        }
    }
    void less_1000(int num, string& ans) {
        if (num / 100 != 0) {
            ans_append(num1[num / 100 - 1], ans);
            ans_append("Hundred", ans);
        }
        if (num / 10 % 10 == 0 && num % 10 != 0) {
            ans_append(num1[num % 10 - 1], ans);
        }
        if (num / 10 % 10 == 1) {
            ans_append(num2[num % 10], ans);
        }
        if (num / 10 % 10 > 1) {
            ans_append(num3[num / 10 % 10 - 2], ans);
            if (num % 10 != 0) {
                ans_append(num1[num % 10 - 1], ans);
            }
        }
    }
public:
    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        string ans = "";
        if (num / 1000000000 != 0) {
            less_1000(num / 1000000000, ans);
            ans_append("Billion", ans);
        }
        if (num / 1000000 % 1000 != 0) {
            less_1000(num / 1000000 % 1000, ans);
            ans_append("Million", ans);
        }
        if (num / 1000 % 1000 != 0) {
            less_1000(num / 1000 % 1000, ans);
            ans_append("Thousand", ans);
        }
        if (num % 1000 != 0) {
            less_1000(num % 1000, ans);
        }
        return ans;
    }
};